package j2025.j03;


/**
 * @Author 猫大仙
 */
class Listnode {
    int val;
    Listnode next;
    Listnode() {}
    Listnode(int val) { this.val = val; }
    Listnode(int val, Listnode next) { this.val = val; this.next = next;
    }}

public class j0306 {
    public Listnode reverseList(Listnode head) {
        if(head==null || head.next==null) return head;
        Listnode newhead = reverseList(head.next);
        //(i+1)结点的下一个为i
        head.next.next = head;
        head.next = null;
        return newhead;
    }

    /**
     * 234. 回文链表
     * 给你一个单链表的头节点 head ，请你判断该链表是否为
     * 回文链表
     * 。如果是，返回 true ；否则，返回 false 。
     */
    public boolean isPalindrome(Listnode head) {
        if(head==null){
            return true;
        }
        Listnode front = half(head);
        Listnode back = reverseList(front);
        Listnode p1 = head;
        Listnode p2 = back;
        boolean ret = true;
        while(ret && p2!=null){
            if(p1.val!=p2.val){
                ret = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        front.next = reverseList(back);
        return ret;
    }
    public Listnode half(Listnode head) {
        Listnode slow = head;
        Listnode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}
